/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-30
 * Time: 23:26
 */


import java.util.*;

/**
 *  图用邻接矩阵表示
 */
public class GraphByMatrix {

    public HashMap<Character, Integer> nodes; // 存储节点以及其对应的下标, 是为了能通过节点获取下标
    public char[] nodeArray; // 也是存储节点及其对应的下标, 为了能够根据下标 获取到对应的节点
    public int[][] matrix; // 邻接矩阵
    public boolean isDirect; // 是否是有向图

    public GraphByMatrix(int num, boolean isDirect){
        this.nodes=new HashMap<>();
        this.nodeArray=new char[num];
        this.matrix=new int[num][num];
        // 为了能够表示权值, 不直接相连的赋值为 无穷
        for (int[] ints : matrix) {
            // 赋初值, 只能一次给一维数组赋值
            Arrays.fill(ints, Constant.MAX);
        }
        this.isDirect=isDirect;
    }

    public void initNodes(char[] nodeArr){
        for (int i=0;i<nodeArr.length;i++) {
            char c=nodeArr[i];
            nodeArray[i]=c;
            nodes.put(c, i);
        }
    }

    /**
     * 添加边
     * @param src 源节点
     * @param dest 目的节点
     * @param weight 边的权重
     */
    public void addEdge(char src, char dest, int weight){
        int srcIndex=nodes.get(src);
        int destIndex=nodes.get(dest);
        matrix[srcIndex][destIndex]=weight;
        if(!isDirect){
            // 如果是无向图, 那么需要对称的增加边
            matrix[destIndex][srcIndex]=weight;
        }
    }

    /**
     * 获取一个节点的 度, 对于有向图= 入度 + 出度
     * @param c
     * @return
     */
    public int getDegree(char c){
        int index=nodes.get(c); // 节点对应的下标
        int count=0;
        // 这里只是计算了 出度
        for (int i = 0; i < matrix[index].length; i++) {
            if(matrix[index][i]!=Constant.MAX){
                count++;
            }
        }
        // 如果是 有向图, 还需要计算入度
        if(isDirect){
            for (int i = 0; i < matrix.length; i++) {
                if(matrix[i][index]!=Constant.MAX){
                    count++;
                }
            }
        }
        return count;
    }


    /**
     *  打印图的邻接矩阵
     */
    public void printGraph(){
        System.out.print("  ");
        for (char c: nodeArray) {
            System.out.print(c+" ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            System.out.print(nodeArray[i]+" ");
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j]!=Constant.MAX){
                    System.out.print(matrix[i][j]+" ");
                }else{
                    System.out.print("∞ ");
                }
            }
            System.out.println();
        }
    }

    /**
     *  广度优先遍历
     * @param charV 起始点
     */
    public void bfs(char charV) {
        // 记录节点是否已经被遍历过了
        boolean[] isVisited = new boolean[nodeArray.length];
        int srcIndex = nodes.get(charV);
        // 定义队列辅助完成广度优先遍历
        Queue<Integer> queue = new LinkedList<>();
        queue.add(srcIndex);
        while (!queue.isEmpty()) {
            srcIndex = queue.poll();
            System.out.print(nodeArray[srcIndex] + " ");
            isVisited[srcIndex] = true;  // 每出队列一个就将该节点置为 true, 防止重复遍历
            // 不用记录 count , 因为 只要队列为空, 就说明已经遍历完了
//            if(count==nodeArray.length){
//                break;
//            }
            for (int i = 0; i < matrix[srcIndex].length; i++) {
                if (matrix[srcIndex][i] != Constant.MAX && !isVisited[i]) {
                    // 每放进去一个节点就置为 true, 是为了防止队列中出现相同的节点
                    isVisited[i] = true;
                    queue.add(i);
                }
            }
        }
        System.out.println();
    }

    /**
     * 深度优先遍历
     * @param srcV 起始点
     */
    public void dfs(char srcV){
        int srcIndex=nodes.get(srcV);
        // 记录节点是否已经被遍历过了
        boolean[] isVisited = new boolean[nodeArray.length];
        dfsChild(srcIndex, isVisited);
    }

    private void dfsChild(int srcIndex, boolean[] isVisited ) {
        isVisited[srcIndex]=true;
        System.out.print(nodeArray[srcIndex]+" ");
        for (int i = 0; i < matrix[srcIndex].length; i++) {
            if(matrix[srcIndex][i]!=Constant.MAX&&!isVisited[i]){
                dfsChild(i, isVisited);
            }
        }
    }


    static class Edge{
        public int srcIndex;
        public int destIndex;
        public int weight;

        public Edge(int srcIndex, int destIndex, int weight) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }
    /**
     *  克鲁斯卡尔算法求最小生成树
     * @param minTree 求出的最小生成树
     */
    public int kruskal(GraphByMatrix minTree){
        PriorityQueue<Edge> minHeap=new PriorityQueue<>(((o1, o2) -> o1.weight-o2.weight));
        // 把所有的边添加到优先级队列中
        for (int i = 0; i < matrix.length; i++) {
            // kruskal 和 prim 算法都是针对无向图的, 所以只用遍历一半就可以了
            for (int j = i+1; j<matrix[i].length; j++) {
                if(matrix[i][j]!=Constant.MAX){
                    // 添加到队列中
                    minHeap.add(new Edge(i,j,matrix[i][j]));
                }
            }
        }

        // 使用并查集来判断是否形成环
        UnionFindSet unionFindSet=new UnionFindSet(nodeArray.length); // 合并的都是节点
        int count=0; // 记录已经选择的边数,用来判断是否最小生树是否选择完成
        int totalWeight=0; // 记录最小生成树的权重
        // 开始选择 权值最小的边
        while(!minHeap.isEmpty()){
            Edge edge=minHeap.poll();
            int srcIndex=edge.srcIndex;
            int destIndex= edge.destIndex;
            if(!unionFindSet.isSameUnionFindSet(srcIndex, destIndex)){
                // 如果这条边的左右两个顶点 不在同一个集合里面了, 那么就会形成环
                // 将边添加进去
                minTree.matrix[srcIndex][destIndex]=edge.weight;
                if(!isDirect){
                    // 如果是无向图, 那么需要对称设置
                    minTree.matrix[destIndex][srcIndex]=edge.weight;
                }
                System.out.println(nodeArray[srcIndex]+" -> "+nodeArray[destIndex]+" "+ edge.weight);
                // 不要忘记更新并查集
                unionFindSet.union(srcIndex, destIndex);
                count++;
                totalWeight+= edge.weight;
                if(count==nodeArray.length-1){
                    // 最小生成树已经选择完成
                    return totalWeight;
                }
            }

        }
        return -1;  // -1 说明没有最小生成树
    }

    /**
     *  普利姆算法求最小生成树
     * @param minTree
     */
    public int prim(GraphByMatrix minTree, char srcV){
        int srcIndex=nodes.get(srcV);
        PriorityQueue<Edge> minHeap=new PriorityQueue<>((o1, o2) -> o1.weight- o2.weight);
        int count=0; // 记录已经添加进去的边的条数
        int totalWeight=0;
        // 记录还未添加进去的节点
        Set<Character> notAddSet=new HashSet<>();
        for (int i = 0; i < nodeArray.length; i++) {
            notAddSet.add(nodeArray[i]);
        }
        notAddSet.remove(srcV);

        // 将起始节点连接的所有边添加到优先级队列中
        for (int i = 0; i < matrix[srcIndex].length; i++) {
            if(matrix[srcIndex][i]!=Constant.MAX){
                minHeap.add(new Edge(srcIndex, i, matrix[srcIndex][i]));
            }
        }
        // 开始选择边
        System.out.println("选择的边: ");
        while(!minHeap.isEmpty()){
            // 找到连通分支中最小的未被选择的边
            Edge minEdge=minHeap.poll();
            int srcI=minEdge.srcIndex;
            int destI=minEdge.destIndex;
            if(!notAddSet.contains(nodeArray[destI])){
                System.out.println("构成环的边"+nodeArray[srcI]+"->"
                +nodeArray[destI]+": "+matrix[srcI][destI]);
            }else{
                // 添加到最小生成树中
                minTree.matrix[srcI][destI]= minEdge.weight;
                if(!isDirect){
                    // 如果是无向图, 那么需要对称设置
                    minTree.matrix[destI][srcI]= minEdge.weight;
                }
                System.out.println(nodeArray[srcI]+"->"+nodeArray[destI]+": "+matrix[srcI][destI]);
                // 从没有被选过的集合中删除
                notAddSet.remove(nodeArray[destI]);
                totalWeight+= minEdge.weight;
                count++;
                if(count==nodeArray.length-1){
                    return totalWeight;
                }
                // 更新 srcIndex
                srcIndex= destI;
                // 把 destI 连接出去的所有边也放到优先级队列中
                for (int i = 0; i < matrix[srcIndex].length; i++) {
                    // 添加进去的这条边需要保证 连接的那个节点还没有被 添加进去
                    // 这样直接就保证了 不会出现环
                    if(matrix[srcIndex][i]!=Constant.MAX&& notAddSet.contains(nodeArray[i])){
                        minHeap.offer(new Edge(srcIndex,i,matrix[srcIndex][i]));
                    }
                }
            }
        }
        return -1;
    }


    /**
     *  迪杰斯特拉 求单源最短路径 (缺点是, 搞不定带有负权的路径)
     * @param srcV 起始节点
     * @param dist 路径距离数组
     * @param path 路径数组
     */
    public void dijkstra(char srcV, int[] dist, int[] path){
        int srcIndex=nodes.get(srcV);
        // 路径数组初始化
        Arrays.fill(path, -1);
        // 距离数组初始化
        Arrays.fill(dist, Constant.MAX);
        dist[srcIndex]=0;
        int length=nodeArray.length;
        // 标记达到该点的路径是否已经被确定下来了
        boolean[] isDecided=new boolean[length];
        isDecided[srcIndex]=true;

        // n 个顶点, 需要更新 n 次, 每次确定一个节点
        for (int k = 0; k < length; k++) {
            int minDist=Constant.MAX;
            for (int i = 0; i < length; i++) {
                if(dist[i]<minDist&&!isDecided[i]){
                    srcIndex=i;
                    minDist=dist[i];
                }
            }
            // 将该节点置为 true
            isDecided[srcIndex]=true;

            // 根据新确定的点去对其他相邻的点进行松弛操作
            for (int i = 0; i < matrix[srcIndex].length; i++) {
                // 如果新的路径比之前的路径短, 那么就更新为最新的路径
                if(!isDecided[i] && matrix[srcIndex][i]!=Constant.MAX  &&
                        dist[srcIndex]+matrix[srcIndex][i]<dist[i]){
                    // 更新为最短的距离
                    dist[i]=dist[srcIndex]+matrix[srcIndex][i];
                    // 记录一下是从哪个节点到该节点的
                    path[i]=srcIndex;
                }
            }
        }
    }

    /**
     *  打印最短的路径
     * @param srcV 起始点
     * @param dist 距离数组
     * @param path 路径数组
     */
    public void printShortPath(char srcV, int[] dist, int[] path){
        int srcIndex=nodes.get(srcV);
        int length=dist.length;
        for (int i = 0; i < length; i++) {
            List<Integer> list=new ArrayList<>();
            int j=i;
            while(path[j]>=0){
                list.add(j);
                j=path[j];
            }
            list.add(j);
            // 集合反转得到的才是从 src 到 dest 的路径
            // 否则是 从 dest 到 src 的路径
            Collections.reverse(list);
            for (int x: list) {
                System.out.print(nodeArray[x]+"->");
            }
            System.out.println("最短路径为: "+ dist[i]);
        }
    }


    /**
     *  贝尔曼-福特 求带有负权路径的单源最短路径
     *  是一种暴力求解的方法, 时间复杂度为 O(n^3)
     * @param srcV 源节点
     * @param dist 距离数组
     * @param path 路径数组
     */
    public boolean bellmanFord(char srcV, int[] dist, int[] path){
        int srcIndex=nodes.get(srcV);
        // 初始化距离数组
        Arrays.fill(dist, Constant.MAX);
        dist[srcIndex]=0;
        // 初始化路径数组
        Arrays.fill(path, -1);
        int length=nodeArray.length;
        // 暴力求解
        // 因为有负权路径, 当松弛完一遍之后, 可能有的节点的最短路径被更新了, 那么与它连接的其他节点的路径, 也要更新
        // 一遍松弛确定一个点, 所以要全面松弛 length 遍
        for (int k = 0; k < length; k++) {
            // 直接对每个节点进行松弛
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if(matrix[i][j]!=Constant.MAX&&
                    dist[i]+matrix[i][j]<dist[j]){
                        dist[j]=dist[i]+matrix[i][j];
                        path[j]=i;
                    }
                }
            }
        }
        // 再对每个节点进行松弛, 如果还有节点的最短路径需要更新
        // 说明出现了 负权回路, 本身就是一个有问题的图, 没有办法求出最短路径
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if(matrix[i][j]!=Constant.MAX&&
                        dist[i]+matrix[i][j]<dist[j]){
                    return false;
                }
            }
        }
        return true;
    }


    /**
     *  floydWarshall
     *  求带负权的多源最短路径
     * @param dist
     * @param path
     */
    public void floydWarshall(int[][] dist, int[][] path){
        int length=nodeArray.length;
        for (int i = 0; i < length; i++) {
            Arrays.fill(dist[i], Constant.MAX);
            dist[i][i]=0;
            Arrays.fill(path[i],-1);
        }

        // 对原本就相连的节点进行更新
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if(matrix[i][j]!=Constant.MAX){
                    dist[i][j]=matrix[i][j];
                    path[i][j]=i;
                }
            }
        }
        // k  表示要经过的节点
        // 最终找的的是 经过其中某一个或某几个点后的最短路径
        for (int k = 0; k < length; k++) {
            // i 表示起点
            for (int i = 0; i < length; i++) {
                // j 表示终点
                for (int j = 0; j < length; j++) {
                    // 注意这里的 i j k 的顺序
                    if( dist[i][k]!=Constant.MAX && dist[k][j]!=Constant.MAX &&
                    dist[i][k]+dist[k][j]<dist[i][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];
                        // 这里注意, path[i][k] 记录的是到达 k节点的前一个节点
                        // 有上面的判断条件可知道 , 这个节点一定与 path[j][k] 相同
                        // 因为 path[j][k] 记录的就是到达 k节点的前一个节点, 而我们使用了这条路径
                        path[i][j]=path[k][j];  // 所以  path[i][k]=j 是不对的
                    }
                }
            }
        }

        // 测试, 打印权值和路径
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if(dist[i][j]!=Constant.MAX){
                    System.out.print(dist[i][j]+" ");
//                    System.out.print(nodeArray[i]+"->"+nodeArray[j]+"最短路径为: "+ dist[i][j]);
                }else{
                    System.out.print("∞ ");
                }
            }
            System.out.println();
        }

        System.out.println("=========打印路径==========");
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                System.out.print(path[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("=================");
    }
}
